/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86131
 * Date: 2023-11-29
 * Time: 16:40
 */
public class MySingleList implements IList {
    static class ListNode {  //静态内部类
        public int value;
        public ListNode next; //因为next是指向结点的,所以是ListNode类型

        public ListNode(int value) {  //实例化结点的时候不知道next指向谁,所以不用next构造
            this.value = value;
        }
    }

    //链表的属性,链表的头结点
    //不能创建在内部类里,否则成为新结点的头结点
    public ListNode head;  //null

    public void creatList() { //方法执行完后,里面的局部变量node1...都会被回收掉,链表还存在
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        this.head = node1;
    }

    //头插法
    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);  //创建一个新结点
        node.next = this.head;  //先让新节点的next指向head,然后head指针走向node
        this.head = node;
    }

    //尾插法
    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);  //创建一个新结点

        if (head == null) {
            head = node;   //分两种情况,如果链表是空的
        } else {
            ListNode cur = head;  //定义一个cur代替head去遍历

            while (cur.next != null) { //执行完循环后cur就指向最后一个元素了
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    @Override
    public void addIndex(int index, int data) throws indexException {
        //判断index是否合法
        if (index < 0 || index > size()) {
            throw new indexException("index不合法: " + index);
        }
        ListNode node = new ListNode(data);
        if (head == null) {  //链表为空
            head = node;
            return;
        }
        //如果索引为0,直接头插法
        if (index == 0) {
            addFirst(data);
            return;
        }

        //如果索引为链表长度,直接尾插法
        if (index == size()) {
            addLast(data);
            return;
        }

        //中间插入
        ListNode cur = searchPrevIndex(index);  //cur指向index前一个位置
        node.next = cur.next;  //先把要插入的结点node的next指向cur的next
        cur.next = node;  //cur的next再指向node,不然会丢失

    }

    private ListNode searchPrevIndex(int index) {  //找index前一个位置
        ListNode cur = head;  //定义一个cur代替head去遍历
        int count = 0;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    //求当前链表是否存在Key
    @Override
    public boolean contains(int key) {
        ListNode cur = head;  //定义一个cur代替head去遍历
        while (cur != null) {  //循环执行完后cur指向尾结..点的后一个位置,也就是null
            if (cur.value == key) {
                System.out.println("元素存在");
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        //链表为空
        if (head == null) {
            return;
        }
        //删除的关键字是头结点
        if (head.value == key) {
            head = head.next;  //直接指向头结点的下一位
            return;
        }
        //删除操作
        ListNode cur = findPrevKey(key);
        if (cur == null) {
            System.out.println("没有你要删除的数字");
            return;
        } else {
            cur.next = cur.next.next;   //直接指向要删除的下下个结点
        }
    }

    private ListNode findPrevKey(int key) {  //找322去    到要删除结点的前驱才能
        ListNode cur = head;  //定义一个cur代替head去遍历
        while (cur.next != null) {
            if (cur.next.value == key) {
                return cur;
            } else {
                cur = cur.next;
            }
        }
        return null;
    }

    @Override
    public void removeAllKey(int key) {
        if (head == null) {
            return;
        }

        while (head.value == key) { //会出现重复要删除的头结点,所以要用循环判断
            head = head.next;
            return;
        }
        ListNode cur = head.next;  //定义一个cur代替head去遍历
        ListNode prev = head; //代表要删除结点的前驱
        while (cur != null) {
            if (cur.value == key) {
                prev.next = cur.next;  //这一步cur的前驱直接跳过cur结点,指向cur的后继
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
    }

    //求链表有多少个结点
    @Override
    public int size() {
        int count = 0;
        ListNode cur = head;  //定义一个cur代替head去遍历
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //清空
    @Override
    public void clear() {
        head = null;  //当一个对象没人引用的时候就会被回收
    }

    @Override
    public void display() {
        ListNode cur = head;  //定义一个cur代替head去遍历
        while (cur != null) { //指向空就退出循环
            System.out.println(cur.value + " ");
            cur = cur.next;  //从当前结点走到下个结点
        }
    }

    public ListNode partition(int x) {
        // write code here
        //定义一个cur指向头结点
        ListNode cur = head;
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;

        while (cur != null) {
            if (cur.value < x) {
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            } else { //这里就 >=
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
                cur = cur.next;
            }
        }
        be.next = as;
        return bs;
    }

    //判断是否是回文结构
    public boolean chkPalindrome(ListNode A) {
        // write code here
        if (head == null) {
            return false;
        }
        //1.找中间结点
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //2.翻转
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //3.一个往前,一个往后
        while (slow != head) {
            if (slow.value != head.value) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;

    }


}
